1. Field of the Invention
The present invention relates to a computer network system, and more particularly pertains to the art of detecting a deadlock over multiple nodes and releasing it.
2. Description of the Related Art
In a network system there is a possibility that a global deadlock and a local deadlock occur. A "global deadlock" is a situation where a plurality of programs running on multiple computer systems (nodes) each wait for one of the other programs to be released from a wait state and in such a way that none of the programs come out of the wait state. A "local deadlock" is a situation where multiple programs running on a single computer system each wait for another's release from wait state and cannot come out of the wait state.
The following are three conventional ways to detect a global deadlock:
(i) Distributed type: Detects a global deadlock using local deadlock detection information for each computer system. PA1 (ii) Copied type: Individual computer systems have the same deadlock detection information and separately detect a global deadlock. PA1 (iii) Centralized type: One of multiple computer systems detects the occurrence of a deadlock.
The distributed deadlock detection method is the best from the view point of reduction of overhead and the amount of information about deadlock detection. The disadvantage of the distributed method, however, is that it is difficult to insure the consistency of the deadlock detection information of multiple computer systems, and it is therefore difficult to accurately detect the occurrence of a deadlock.
There are network systems which link computer systems of different types. In such network systems each computer system monitors the time difference between the making a request to another computer system and the returning of a response therefrom. Each computer system determines that a deadlock has occurred when the target computer system does not respond within a given period of time. The disadvantage of deadlock detection method is that the detection accuracy depends greatly on the length of the monitoring time.
Various ways to detect deadlocks are described in Mukesh Singhal, Deadlock Detection in Distributed Systems, in IEEE Computer, November 1989, PP 37-48. The contents of this article are incorporated in this specification as a reference.